#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:

    // 560. 和为 K 的子数组
    // https://leetcode.cn/problems/subarray-sum-equals-k/
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int sum = 0;
        int ans = 0;

        hash[0] = 1;
        for (auto num : nums)
        {
            sum += num;
            if (hash.count(sum - k))
                ans += hash[sum - k];
            ++hash[sum];
        }

        return ans;
    }

    // 974. 和可被 K 整除的子数组
    // https://leetcode.cn/problems/subarray-sums-divisible-by-k/
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0;
        int ans = 0;
        
        unordered_map<int, int> hash;
        hash[0] = 1;
        for (auto num : nums)
        {
            sum += num;

            if (hash.count( (sum % k + k ) % k ))
                ans += hash[(sum % k + k ) % k];
            ++hash[(sum % k + k ) % k];
        }

        return ans;
    }
};